<?php

/**
 * 最接近的三数之和
 * Class Solution
 */
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function threeSumClosest($nums, $target) {

        sort($nums);

        $len=sizeof($nums);

        $min=false;

        $recentTarget=0;
        for($i=0;$i<$len;$i++){

            $left=$i+1;
            $right=$len-1;


            $first=$nums[$i];

            while($left<$right){

                $thirdZero=$target-$first-$nums[$left];

                $diff=abs($nums[$right]-$thirdZero);

                while($left<($right-1) && abs($nums[$right-1]-$thirdZero)<=$diff){
                    $right--;
                    $diff=abs($nums[$right]-$thirdZero);
                }
                if($diff<=$min || $min===false){
                    $min=$diff;
                    $recentTarget=$first+$nums[$left]+$nums[$right];
                }
                $left++;
                $right=$len-1;
            }
        }
        return $recentTarget;
    }
}
